package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/15 16:47
 * @description: 力扣70题 爬楼梯
 */
public class ClimbStairs {

    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        System.out.println(new ClimbStairs_Solution().climbStairs1(n));
        System.out.println(new ClimbStairs_Solution().climbStairs2(n));
    }
}


class ClimbStairs_Solution{
    public int climbStairs1(int n){
        int []dp = new int[n+1];
        dp[0] = 1;
        for(int i = 1;i <= n;i++){
            dp[i] = dp[i-1];
            if(i > 1){
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
    public int climbStairs2(int n){
        int p = 0,q,r =1;
        for(int i =0;i < n;i++){
            q = p;
            p = r;
            r = 0;
            r += p;
            if(i == 0){
                continue;
            }
            r += q;
        }
        return r;
    }
}
